import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

/**
 * 合并两个已经排序好的链表。
 */
public class JavaDemo15 {
    public static void main(String[] args) {
        int[] arrays = {1, 3, 5};
        ListNode head = new ListNode(0);
        ListNode next = head;
        for (int i = 0; i < arrays.length; i++) {
            ListNode node = new ListNode(arrays[i]);
            next.next = node;
            next = node;
        }
        ListNode head1 = new ListNode(2);
        ListNode next1 = head1;
        int[] arrays1 = {4, 6, 8};
        for (int i = 0; i < arrays1.length; i++) {
            ListNode node = new ListNode(arrays1[i]);
            next1.next = node;
            next1 = node;
        }
        // 0,1,3,5，和2,4,6,8合并。
        ListNode merge = mergeNode(head, head1);
        ListNode showParent = merge;
        while (showParent != null) {
            System.out.println(showParent.val);
            showParent = showParent.next;
        }
    }

    /**
     * 合并两个node
     *重新创建链表
     * @param head
     * @param head1
     * @return
     */
    private static ListNode mergeNode(ListNode head, ListNode head1) {
        ArrayList<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        while (head1 != null) {
            list.add(head1.val);
            head1 = head1.next;
        }
        Collections.sort(list);
        ListNode newHead =new ListNode(list.get(0));
        ListNode cur=newHead;
        for (int i=1;i<list.size();i++){
            cur.next=new ListNode(list.get(i));
            cur=cur.next;
        }
        return newHead;
    }
}
